package com.coder.algorithm.offer_2;

/**
 * 丑数
 *
 * @author yuhushuan
 * @date 2020/6/28 11:54
 */
public class _49_1_UglyNumber {
    private static int getUglyNumber(int index) {
        if (index <= 0) {
            return 0;
        }
        int number = 0;
        int uglyFound = 0;
        while (uglyFound < index) {
            number++;
            if (isUglyNumber(number)) {
                uglyFound++;
            }
        }
        return number;
    }

    private static boolean isUglyNumber(int number) {
        while (number % 2 == 0) {
            number /= 2;
        }
        while (number % 3 == 0) {
            number /= 3;
        }
        while (number % 5 == 0) {
            number /= 5;
        }
        return number == 1;
    }

    private static int getUglyNumber_solution2(int index) {
        if (index <= 0) {
            return 0;
        }
        int[] uglyNumbers = new int[index];
        uglyNumbers[0] = 1;

        int nextUglyIndex = 1;

        // multiply 记录上一次计算后为最小丑数的因子。
        int multiply2 = 0;
        int multiply3 = 0;
        int multiply5 = 0;

        while (nextUglyIndex < index) {
            int min = getMin(uglyNumbers[multiply2] * 2, uglyNumbers[multiply3] * 3, uglyNumbers[multiply5] * 5);
            uglyNumbers[nextUglyIndex] = min;

            while (uglyNumbers[multiply2] * 2 <= min) {
                multiply2++;
            }
            while (uglyNumbers[multiply3] * 3 <= min) {
                multiply3++;
            }
            while (uglyNumbers[multiply5] * 5 <= min) {
                multiply5++;
            }

            nextUglyIndex++;
        }
        return uglyNumbers[nextUglyIndex - 1];
    }

    private static int getMin(int number1, int number2, int number3) {
        int min = number1;
        if (number2 < min) {
            min = number2;
        }
        if (number3 < min) {
            min = number3;
        }
        return min;
    }

    public static void main(String[] args) {
        // 功能测试
        print(2);
        print(3);
        print(4);
        print(5);
        print(6);

        // 特殊输入测试
        print(1);
        print(0);

        // 性能测试
        print(1500);
    }

    private static void print(int index) {
        System.out.println("第 " + index + " 个丑数为：");
        long time = System.currentTimeMillis();
        System.out.println("解法一：" + getUglyNumber(index) +
                " 耗时：" + (System.currentTimeMillis() - time) + "ms");
        time = System.currentTimeMillis();
        System.out.println("解法二：" + getUglyNumber_solution2(index) +
                " 耗时：" + (System.currentTimeMillis() - time) + "ms");
        System.out.println();
    }
}
